package com.magupe.develop.algorithm;

import java.util.Arrays;

/**
 *
 * @author
 */
public class Main2 {

    public static void main(String[] args) {
        int[] array = new int[]{50, 10, 90, 30, 70, 40, 80, 60};
        mergeSort(array, 0, array.length - 1);
    }

    /**
     * 归并排序
     *
     * @param a
     * @param start
     * @param end
     */
    public static void mergeSort(int[] a, int start, int end) {
        int mid = (start + end) / 2;
        // 当子序列中只有一个元素时结束递归
        if (start < end) {
            // 对左侧子序列进行递归排序
            mergeSort(a, start, mid);
            // 对右侧子序列进行递归排序
            mergeSort(a, mid + 1, end);
            // 合并
            merge(a, start, mid, end);
        }
    }

    public static void merge(int[] a, int left, int mid, int right) {
        // 辅助数组
        int[] tmp = new int[a.length];
        // p1、p2是检测指针，k是存放指针
        int p1 = left, p2 = mid + 1, k = left;

        if(right == 3){
            System.out.println("");
        }
        while(p1 <= mid && p2 <= right){
            if(a[p1] <= a[p2]) {
                tmp[k] = a[p1];
                p1++;
            } else {
                tmp[k] = a[p2];
                p2++;
            }
            k++;
        }
        // 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p1 <= mid) {
            tmp[k] = a[p1];
            k++;
            p1++;
        }
        // 同上
        while(p2 <= right) {
            tmp[k] = a[p2];
            k++;
            p2++;
        }
        // 复制回原素组
        for (int i = left; i <=right; i++){
            a[i]=tmp[i];
        }
        System.out.println(left + ", " + right);
        System.out.println(Arrays.toString(a));
    }
}
